\documentclass[a4paper, 10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}

\renewcommand{\shorthandsspanish}{}

\newcommand{\HRule}{\rule{\linewidth}{0.5mm}}

\begin{document}
\begin{titlepage}
\begin{center}

\textsc{\LARGE Autómatas, Teoría de Lenguajes y Compiladores}\\[1.5cm]
\textsc{\Large Trabajo Práctico Especial 2}\\[0.5cm]

\HRule \\[0.4cm]
 {\huge \bfseries Máquina de Turing}\\[0.4cm]
\HRule \\[1.5cm]


\Large Grupo 1: \\ [0.25cm]
\begin{tabular}{l @{\ \ -\ \ }l}

\emph{\Large Ballesty, Pablo Andres} & \Large 49359\\[0.2cm]
\emph{\Large Castro Peña, Gonzalo} & \Large 49398\\[0.2cm]
\emph{\Large Perez Cuñarro, Javier} & \Large 49729\\[0.2cm]

\end{tabular}

\vspace{9cm}

\textsc{\Large Primer cuatrimestre 2011}
\vspace{4cm}

\end{center}
\end{titlepage}

\clearpage

%%%%%%%%%%%%

\tableofcontents
\clearpage

%%%%%%%%%%%%%%%%
\section{Introducción}

Este trabajo consistió en desarrollar una implementación de la máquina de Turing, que se basa en una variante especificada por la cátedra.\\

Para resolver este trabajo, se optó por Java para el programa. Se utilizó el entorno de desarrollo Eclipse, con la ayuda del plugin de Maven.\\

%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Consideraciones realizadas}

\begin{itemize}

\item El programa exije especificar, mediante línea de comandos, un único archivo que contenga una única máquina de Turing. De no especificarlo, el programa no correrá (no existe un archivo default del cual se levante una máquina preestablecida), y se informará al usuario del error cometido. Una invocación correcta sería:
\\
\\\begin{tt}
\$ ./mt maquinauno.mt
\end{tt}\\\\
En cambio, invocaciones incorrectas son:
\\
\\\begin{tt}
\$ ./mt
\end{tt}\\
\\\begin{tt}
\$ ./mt maquinauno.mt maquinados.mt
\end{tt}\\

\item Este archivo exigido debe tener el formato que indica el enunciado del trabajo práctico. Cada línea debe tener el siguiente aspecto:
\\
\\\begin{tt}
estado origen,simbolo en cinta,estado destino,accion
\end{tt}\\\\
Todos los estados deben ser combinaciones alfanuméricas, los símbolos deben ser "0", "1" o "2" obligatoriamente, y las acciones deben ser movimientos izquierda/derecha o reemplazo de símbolos por otros también válidos.\\\\
No se permite la inclusión de espacios entre comas, símbolos de separación que no sean comas, espacios dentro de nombres de estados, o espacios al finalizar una línea.\\\\
A su vez, debe existir una sola transición por línea. No deben haber líneas en blanco, ni líneas que no cumplan con este formato. \\\\
Un ejemplo de línea permitida es:
\\
\\\begin{tt}
q0,0,q1,>
\end{tt}\\\\
que se traduce como \textit{"estando en estado q0, si el símbolo actual de la cinta es 0, paso al estado q1 y muevo el cabezal de la cinta al símbolo inmediatamente a la derecha"}.\\\\
El programa no entiende las siguientes líneas:
\\
\\\begin{tt}
est   ado,0,q1,>
\end{tt}\\
\\\begin{tt}
q0,8,q1,>
\end{tt}\\
\\\begin{tt}
q0;0;q1;>
\end{tt}\\\\
Cabe destacar que tampoco se permiten máquinas de Turing mal formadas. En particular, si se especifican dos o más transiciones para un estado origen y un mismo símbolo en cinta, se alerta al usuario de la presencia de transiciones ambiguas y se finaliza la ejecución del programa.\\\\
En caso de no cumplir con todas las condiciones enumeradas, se informa al usuario de que no se correrá el programa ya que no hay una máquina de Turing correcta con la cual operar sobre una cinta. Para intentar utilizar otra máquina, tendrá que invocar nuevamente el programa con otro archivo como parámetro de entrada.

\item La cinta a utilizar es ingresada por el usuario mediante entrada estándar, inmediatamente luego de que el programa lo pida. Esta cinta debe contener únicamente símbolos permitidos, sin caracteres de separación (guiones, comas, etc.), ni espacios en blanco, ni retornos de carro. Como consecuencia, se aceptan cintas del estilo:
\\
\\\begin{tt}
012102012001201
\end{tt}\\
\\\begin{tt}
1111111111111111111
\end{tt}\\\\
Pero los siguientes ejemplos no se aceptan:
\\
\\\begin{tt}
323520293024090920
\end{tt}\\
\\\begin{tt}
120100120 121020 12 012012 1
\end{tt}\\
\\\begin{tt}
0-1-2-1-0-2-0-1-2-0-0-1-2-0-1
\end{tt}\\\\
El ingreso de la cinta termina únicamente al hacer uso del caracter EOF (end of file).\\\\
Está permitido no ingresar una cinta, oprimiendo EOF sin escribir caracteres. Como en realidad la cinta ingresada está precedida y continuada por el símbolo 0, al exigir una cinta vacía, el programa considera una cinta compuesta únicamente por una cantidad infinita de símbolos 0.

\item El programa acepta una sola cinta por ejecución. Esto significa que, por más que el usuario quiera correr una segunda cinta con la misma máquina de Turing, debe volver a ejecutar el programa de la misma forma que lo hizo antes (volviendo a especificar el archivo en el que se encuentra la máquina).

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Descripción del desarrollo del trabajo}

Para este trabajo se eligió Java, en parte para aprovechar la orientación a objetos. Una máquina de Turing es una instancia de la clase Mt, que contiene un map "transitions" con todas las transiciones declaradas (key: estado inicial, value: listado con las transiciones posibles desde ese estado inicial), el casillero actual de la cinta "head" y el estado actual de la máquina "state".\\
\par Cada transición es una instancia de una subclase de Transition, y por lo tanto cuenta con un estado de origen "origin", un símbolo correspondiente al de la cinta "symbol", y un estado destino "destination". A su vez, cada estado se modela con la clase Status, y cada símbolo, como un Symbol.\\
\par Para representar la cinta usada por la máquina, se creó la clase Square. Cada instancia puede tener un casillero izquierdo y un casillero derecho vinculado. En su defecto, se lo vincula con un casillero con símbolo 0, a fines de representar los casilleros de relleno. 

%%%%%%%%%%%%%%%%%%%%%%%%
\section{Dificultades encontradas}

Aunque no se encontraron grandes dificultades, sí hubo que replantear la forma en que se habían modelado las transiciones permitidas en la máquina. Se resolvió por crear una clase abstracta  Transition, y dos subclases: MovementTransition para manejar el movimiento del cabezal de la cinta, y WriteTransition para sobreescribir el símbolo al cual apunta el cabezal en la cinta.

%%%%%%%%%%%%%%%%%%%%%
\section{Futuras extensiones}

\begin{itemize}

\item Las máquinas admitidas por el programa (y las cintas) podrían aceptar símbolos de otro tipo, ya sean otros números, caracteres alfabéticos, espacios, etc. Implementar esto no sería muy complicado, y permitir espacios por ejemplo, brindaría más potencia a las máquinas que se puedan simular. Al no estar tan restringido, el programa permitiría correr cintas y máquinas más complejas, con mucho más que 3 símbolos.

\item Se podría permitir que los símbolos "de relleno" sean distintos al símbolo 0. Por ejemplo, un símbolo distinto al que se use en la cinta que ingresa el usuario, de forma tal que se eviten los problemas de confundir un casillero vacío con uno que parece vacío pero que realmente está ocupado. De esta forma, no se correría tanto riesgo de que se realicen infinitas transiciones de movimiento, por ejemplo.

\item Una simple modificación consistiría en determinar una máquina de Turing predeterminada, por si el usuario olvida especificar el archivo en el que está guardada una máquina en particular. O más bien, se podría setear un archivo de máquina predeterminado, persistir esta preferencia, y ofrecer un modo de cambiarla cada vez que se ejecute el programa, en lugar de escribir el archivo en cada invocación.

\item Otra modificación - quizás más útil - sería permitir el ingreso de más de una cinta dado una ejecución del programa. Esto surge a partir de que, si un usuario quiere probar una misma máquina con varias cintas, debe volver a invocar el programa varias veces ya que el mismo se finaliza al resolver una sola cinta. Otra vez más, implementar esto sería muy sencillo.

\item Una última extensión posible sería la introducción de un gráfico de estados. Utilizando graphviz se podría mostrar el grafo que representa la máquina de Turing del archivo correspondiente, agregando un nuevo argumento de línea de comando. La complejidad no pasa tanto por manejar este argumento, sino por integrar el graphviz con los datos de las transiciones.

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%
\section{Conclusiones}
Este trabajo resultó útil para evaluar las capacidades de las distintas máqunas de Turing. En particular, al pensar en ejemplos para correr con esta variante de cinta infinita de símbolos 0, 1 y 2 (con relleno de símbolo 0), se comprendió la limitación de usar un mismo símbolo como parte de la cinta especificada y como relleno (el 0 en este caso).\\
\par A su vez, luego de aprender tanto sobre las propiedades de las máquinas de Turing en las clases teóricas de la cátedra, este trabajo resultó ser una forma interesante (y lógica) para comprobar que Java es un lenguaje "Turing completo".
\end{document}